package com.fulin.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * TODO
 *
 * @Author fulin
 * @Date 2022/9/22 10:48
 **/
public class Num111_二叉树的最小深度 {

    /**
     * 递归的解法
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int L = minDepth(root.left);
        int R = minDepth(root.right);
        return root.left == null || root.right == null ? L + R + 1 : Math.min(L,R) + 1;
    }

    public int minDepth3(TreeNode root){
        if(root == null) return 0;

        int depth = 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            //此时队列中的元素就是树中同一层的节点
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode poll = queue.poll();
                if(poll.left == null && poll.right == null){
                    return depth;
                }
                if(poll.left != null){
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    queue.add(poll.right);
                }
            }
            depth ++;
        }
        return depth;
    }


    /**
     * 广度优先遍历的解法，第一个叶子节点的深度就是需要的值
     * @param root
     * @return
     */
    public int minDepth2(TreeNode root){
        if(root == null) return 0;

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(root,1));
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            TreeNode node = poll.node;
            if(node.right == null && node.left == null){ return poll.depth;}
            if(node.left != null){
                queue.add(new Node(node.left,poll.depth + 1));
            }
            if(node.right != null){
                queue.add(new Node(node.right,poll.depth + 1));
            }
        }
        return 0;
    }

    private static class Node{
        TreeNode node;
        int depth;
        public Node(TreeNode node,int depth){
            this.depth = depth;
            this.node = node;
        }
    }

}
